//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 19 
// 
// Related Topics 树 二叉搜索树 数学 动态规划 二叉树 👍 1720 👎 0

package leetcode.editor.cn;

class UniqueBinarySearchTrees {
    public static void main(String[] args) {
        Solution solution = new UniqueBinarySearchTrees().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int numTrees(int n) {
            // dp[i]表示i个节点共有dp[i]个组成结构
            int[] dp = new int[n + 1];

            // 初始化dp数组，dp[0]需要初始化为1，防止后面相乘为0
            dp[0] = 1;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= i; j++) {  // j来遍历i里面每一个数作为头节点的状态
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }

            return dp[n];
        }*/

        // 递归法，参照labuladong：https://mp.weixin.qq.com/s/kcwz2lyRxxOsC3n11qdVSw
        int[][] map;  // 记录计算过区间的个数

        public int numTrees(int n) {
            map = new int[n + 1][n + 1];
            return count(1, n);
        }

        public int count(int l, int r) {
            // 此时区间不存在，返回null，所以数字为1
            if (r < l) {
                return 1;
            }

            // 如果不为空，直接返回
            if (map[l][r] != 0) {
                return map[l][r];
            }

            int res = 0;
            for (int i = l; i <= r; i++) {
                int left = count(l, i - 1);
                int right = count(i + 1, r);
                res += left * right;
            }

            map[l][r] = res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
